This invention generally relates to Computer Aided Design based (CAD-based) Cartesian mesh generators, and in particular to a highly accurate and robust cubic cell mesh generator capable of generating over 1 trillion cells.
Computer aided design (CAD) software is used to model physical objects. Most CAD software generates files in Standard Tessellation Language (STL) format. Each object in the CAD model is encompassed by a triangular facet surface mesh. The STL file locates the triangular facets via Cartesian coordinates (x, y, z) of the three vertices of each triangle, uniquely defining a plane. FIG. 1a shows a facet defined by vertices 1, 2, and 3. The vertices are numbered via the STL format convention. This facet lies in the x-y plane. Vectors can be drawn from points 1 to 2, from 2 to 3, and from 3 to 1 as indicated by the dashed lines. By the right-hand rule, the sense of this facet is in the −z direction.
One mesh generation technique involves defining a volume 10 to encompass a solid object of interest 11. Volumes are usually divided into polyhedrons. Here, the volume is subdivided into small perfect cubes 12 or cells as depicted in FIG. 1b. By casting rays 13 in one of the coordinate directions (−z in FIG. 1b) and saving the intersection locations for each facet hit, the surfaces of each body in the volume can be identified. Once the surfaces are known, the solid is defined and can be filled in as it is written to a file. The space between a ray entering a facet (starting surface location) and exiting another facet (ending surface location) within the volume 10 defines the thickness of the solid in that space. The space between the entry facet and the exit facet is filled in by a continuous line of identical cubes as it is written to a file so that the computer main memory only stores the entry and exit locations requiring minimal main memory. By launching a ray 13 perpendicular from each cell face center of a volume domain face, all shapes are resolved. If needed, rays can be cast in all three coordinate directions to better define the shapes. Since this method only requires memory storage of surface position information, the total number of cells can be extremely large, allowing for a large electrical volume size while maintaining very high resolution. (The electrical volume size is the computational volume size relative to the electromagnetic wavelength being simulated.) However, the accuracy and robustness of this method greatly depends on ray-facet intersection tests that are a key element of the present invention.
The present invention is readily adaptable to the modeling of electromagnetic fields emanating from various antenna configurations and the interaction of electromagnetic radiation with solid objects. This is a complex problem involving the solution of Maxwell's Equations and is greatly simplified if the solid object involved can be defined in terms of perfect cubes since the solution of Maxwell's Equations of a cube is relatively simple. Currently, generating a highly accurate CAD based Cartesian mesh with an extremely large number of cells, requires a massively parallel computing resource. The present invention discloses a simplified method of solving this type of problem involving a memory efficient ray tracing method, a highly accurate ray-facet intersection test, and a novel exact arithmetic tie-breaking algorithm for rays intersecting facet edges and vertices.